class RedBlackTreeNode:
    """
    RedBlackTreeNode represents a node in a Red-Black Tree.

    Attributes:
        data: Data stored in the node.
        color: Color of the node (either 'red' or 'black').
        parent: Parent node.
        left: Left child node.
        right: Right child node.
    """

    def __init__(self, data=None, color='red', parent=None, left=None, right=None):
        """
        Initialize a RedBlackTreeNode with data, color, parent, left, and right child nodes.

        Args:
            data: Data for this node. Defaults to None.
            color: Color of the node. Defaults to 'red'.
            parent: Parent node. Defaults to None.
            left: Left child node. Defaults to None.
            right: Right child node. Defaults to None.
        """
        self.data = data
        self.color = color
        self.parent = parent
        self.left = left
        self.right = right

    def __repr__(self):
        """
        Returns a string representation of the RedBlackTreeNode.

        Returns:
            String representation of the RedBlackTreeNode.
        """
        return f"Node({self.data}, {self.color})"


class RedBlackTree:
    """
    RedBlackTree represents a Red-Black Tree data structure.

    Attributes:
        root: Root node of the tree.
    """

    def __init__(self):
        """
        Initialize an empty Red-Black Tree with no root node.
        """
        self.root = None

    def insert(self, data):
        """
        Insert a node with the given data into the Red-Black Tree.

        Args:
            data: Data for the node to be inserted.
        """
        node = RedBlackTreeNode(data=data, color='red')
        if self.root is None:
            self.root = node
            node.color = 'black'
        else:
            self._insert_helper(self.root, node)
            self._fix_up(node)

    def _insert_helper(self, root, node):
        """
        Helper method to insert a node into the Red-Black Tree.

        Args:
            root: Current root node.
            node: Node to be inserted.
        """
        if node.data < root.data:
            if root.left is None:
                root.left = node
                node.parent = root
            else:
                self._insert_helper(root.left, node)
        else:
            if root.right is None:
                root.right = node
                node.parent = root
            else:
                self._insert_helper(root.right, node)

    def _fix_up(self, node):
        """
        Helper method to fix the Red-Black Tree after insertion.

        Args:
            node: Newly inserted node.
        """
        while node.parent and node.parent.color == 'red':
            if node.parent == node.parent.parent.left:
                uncle = node.parent.parent.right
                if uncle and uncle.color == 'red':
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    if node == node.parent.right:
                        node = node.parent
                        self._left_rotate(node)

                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self._right_rotate(node.parent.parent)
            else:
                uncle = node.parent.parent.left
                if uncle and uncle.color == 'red':
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    if node == node.parent.left:
                        node = node.parent
                        self._right_rotate(node)

                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self._left_rotate(node.parent.parent)

        self.root.color = 'black'

    def _left_rotate(self, node):
        """
        Perform a left rotation on the Red-Black Tree.

        Args:
            node: Node to be rotated.
        """
        right_child = node.right
        node.right = right_child.left
        if right_child.left:
            right_child.left.parent = node
        right_child.parent = node.parent
        if not node.parent:
            self.root = right_child
        elif node == node.parent.left:
            node.parent.left = right_child
        else:
            node.parent.right = right_child
        right_child.left = node
        node.parent = right_child

    def _right_rotate(self, node):
        """
        Perform a right rotation on the Red-Black Tree.

        Args:
            node: Node to be rotated.
        """
        left_child = node.left
        node.left = left_child.right
        if left_child.right:
            left_child.right.parent = node
        left_child.parent = node.parent
        if not node.parent:
            self.root = left_child
        elif node == node.parent.right:
            node.parent.right = left_child
        else:
            node.parent.left = left_child
        left_child.right = node
        node.parent = left_child

    def search(self, data):
        """
        Search for a node with the given data in the Red-Black Tree.

        Args:
            data: Data to be searched.

        Returns:
            True if the node is found, False otherwise.
        """
        return self._search_helper(self.root, data)

    def _search_helper(self, node, data):
        """
        Helper method to search for a node with the given data in the Red-Black Tree.

        Args:
            node: Current node being visited.
            data: Data to be searched.

        Returns:
            True if the node is found, False otherwise.
        """
        if node is None:
            return False
        if node.data == data:
            return True
        if data < node.data:
            return self._search_helper(node.left, data)
        else:
            return self._search_helper(node.right, data)

    def delete(self, data):
        """
        Delete a node with the given data from the Red-Black Tree.

        Args:
            data: Data of the node to be deleted.
        """
        node = self._search_node(self.root, data)
        if node is None:
            return

        self._delete_node(node)

    def _search_node(self, node, data):
        """
        Helper method to search for a node with the given data in the Red-Black Tree.

        Args:
            node: Current node being visited.
            data: Data to be searched.

        Returns:
            Node with the given data if found, None otherwise.
        """
        if node is None or node.data == data:
            return node
        if data < node.data:
            return self._search_node(node.left, data)
        else:
            return self._search_node(node.right, data)

    def _delete_node(self, node):
        """
        Helper method to delete a node from the Red-Black Tree.

        Args:
            node: Node to be deleted.
        """
        if node.left is None or node.right is None:
            y = node
        else:
            y = self._successor(node)

        if y.left is not None:
            x = y.left
        else:
            x = y.right

        if x is not None:
            x.parent = y.parent

        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        if y != node:
            node.data = y.data

        if y.color == 'black':
            self._fix_delete(x)

    def _successor(self, node):
        """
        Find the successor of the given node in the Red-Black Tree.

        Args:
            node: Node for which the successor is to be found.

        Returns:
            Successor node.
        """
        if node.right is not None:
            return self._minimum(node.right)

        parent = node.parent
        while parent is not None and node == parent.right:
            node = parent
            parent = parent.parent

        return parent

    def _minimum(self, node):
        """
        Find the minimum node in the Red-Black Tree.

        Args:
            node: Current node being visited.

        Returns:
            Minimum node.
        """
        while node.left is not None:
            node = node.left
        return node

    def _fix_delete(self, node):
        """
        Helper method to fix the Red-Black Tree after deletion.

        Args:
            node: Node affected by deletion.
        """
        while node != self.root and (node is None or node.color == 'black'):
            if node == node.parent.left:
                sibling = node.parent.right
                if sibling.color == 'red':
                    sibling.color = 'black'
                    node.parent.color = 'red'
                    self._left_rotate(node.parent)
                    sibling = node.parent.right

                if (sibling.left is None or sibling.left.color == 'black') and (sibling.right is None or sibling.right.color == 'black'):
                    sibling.color = 'red'
                    node = node.parent
                else:
                    if sibling.right is None or sibling.right.color == 'black':
                        sibling.left.color = 'black'
                        sibling.color = 'red'
                        self._right_rotate(sibling)
                        sibling = node.parent.right

                    sibling.color = node.parent.color
                    node.parent.color = 'black'
                    sibling.right.color = 'black'
                    self._left_rotate(node.parent)
                    node = self.root
            else:
                sibling = node.parent.left
                if sibling.color == 'red':
                    sibling.color = 'black'
                    node.parent.color = 'red'
                    self._right_rotate(node.parent)
                    sibling = node.parent.left

                if (sibling.right is None or sibling.right.color == 'black') and (sibling.left is None or sibling.left.color == 'black'):
                    sibling.color = 'red'
                    node = node.parent
                else:
                    if sibling.left is None or sibling.left.color == 'black':
                        sibling.right.color = 'black'
                        sibling.color = 'red'
                        self._left_rotate(sibling)
                        sibling = node.parent.left

                    sibling.color = node.parent.color
                    node.parent.color = 'black'
                    sibling.left.color = 'black'
                    self._right_rotate(node.parent)
                    node = self.root

        if node is not None:
            node.color = 'black'

    def _left_left_rotate(self, node):
        """
        Perform a left-left rotation on the Red-Black Tree.

        Args:
            node: Node to be rotated.
        """
        right_child = node.right
        node.right = right_child.left
        if right_child.left:
            right_child.left.parent = node
        right_child.parent = node.parent
        if not node.parent:
            self.root = right_child
        elif node == node.parent.left:
            node.parent.left = right_child
        else:
            node.parent.right = right_child
        right_child.left = node
        node.parent = right_child

    def _right_right_rotate(self, node):
        """
        Perform a right-right rotation on the Red-Black Tree.

        Args:
            node: Node to be rotated.
        """
        left_child = node.left
        node.left = left_child.right
        if left_child.right:
            left_child.right.parent = node
        left_child.parent = node.parent
        if not node.parent:
            self.root = left_child
        elif node == node.parent.right:
            node.parent.right = left_child
        else:
            node.parent.left = left_child
        left_child.right = node
        node.parent = left_child

    def _left_right_rotate(self, node):
        """
        Perform a left-right rotation on the Red-Black Tree.

        Args:
            node: Node to be rotated.
        """
        left_child = node.left
        self._left_rotate(left_child)
        self._right_rotate(node)

    def _right_left_rotate(self, node):
        """
        Perform a right-left rotation on the Red-Black Tree.

        Args:
            node: Node to be rotated.
        """
        right_child = node.right
        self._right_rotate(right_child)
        self._left_rotate(node)

    def _display_helper(self, node):
        """
        Helper method to construct the string representation of the Red-Black Tree.

        Args:
            node: Current node being visited.

        Returns:
            Lines representing the Red-Black Tree, along with the width, height, and middle index.
        """
        if node.right is None and node.left is None:
            line = str(node)
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle

        if node.right is None:
            lines, n, p, x = self._display_helper(node.left)
            s = str(node)
            u = len(s)
            first_line = (x + 1) * " " + (n - x - 1) * "_" + s
            second_line = x * " " + "/" + (n - x - 1 + u) * " "
            shifted_lines = [line + u * " " for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

        if node.left is None:
            lines, n, p, x = self._display_helper(node.right)
            s = str(node)
            u = len(s)
            first_line = s + x * "_" + (n - x) * " "
            second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
            shifted_lines = [u * " " + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

        left, n, p, x = self._display_helper(node.left)
        right, m, q, y = self._display_helper(node.right)
        s = str(node)
        u = len(s)
        first_line = (x + 1) * " " + (n - x - 1) * "_" + s + y * "_" + (m - y) * " "
        second_line = x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
        if p < q:
            left += [n * " "] * (q - p)
        elif q < p:
            right += [m * " "] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2

    def _display(self):
        """
        Returns a string representation of the Red-Black Tree.

        Returns:
            String representation of the Red-Black Tree.
        """
        if self.root is None:
            return "Empty Red-Black Tree"

        lines, *_ = self._display_helper(self.root)
        return "\n".join(lines)

    def __str__(self):
        """
        Returns a string representation of the Red-Black Tree.

        Returns:
            String representation of the Red-Black Tree.
        """
        return self._display()

    def __repr__(self):
        """
        Returns a string that represents a valid Python expression that could be used to recreate the Red-Black Tree.

        Returns:
            A string that represents a valid Python expression.
        """
        if self.root is None:
            return "Empty Red-Black Tree"
        return f"RedBlackTree(root={self.root.data})"


if __name__ == "__main__":
    # Create a new Red-Black Tree
    rb_tree = RedBlackTree()

    # Insert nodes into the Red-Black Tree
    rb_tree.insert(10)
    rb_tree.insert(5)
    rb_tree.insert(15)
    rb_tree.insert(3)
    rb_tree.insert(7)
    rb_tree.insert(12)
    rb_tree.insert(17)
    for i in range(20, 200, 60):
        rb_tree.insert(i)

    # Print the Red-Black Tree structure
    print("Red-Black Tree structure:")
    print(rb_tree)
    # Output:
    # Red-Black Tree structure:
    #       ____10____
    #      /          \
    #   __5__       __15__
    #  /     \     /     \
    # 3       7   12     17

    # Search for a node in the Red-Black Tree
    data = 15
    is_found = rb_tree.search(data)
    print(f"Node {data} is found: {is_found}")
    # Output:
    # Node 15 is found: True

    # Delete a node from the Red-Black Tree
    delete_data = 7
    rb_tree.delete(delete_data)
    print(f"Deleted node {delete_data}")
    print("Red-Black Tree after deletion:")
    print(rb_tree)
    # Output:
    # Deleted node 7
    # Red-Black Tree after deletion:
    #       ____10____
    #      /          \
    #   __5__       __15__
    #  /           /     \
    # 3          12     17
